1. Field of the Invention
This invention relates generally to pipelined processors, and more particularly, to a back end replay mechanism for a processor pipeline.
2. Description of the Related Art
Computers and many other types of machines are engineered around a "processor." A processor is an integrated circuit that executes programmed instructions stored in the machine's memory. There are many types of processors and there are several ways to categorize them. For instance, one may categorize processors by their intended application, such as microprocessors, digital signal processors ("DSPs"), or controllers. One may also categorize processors by the complexity of their instruction sets, such as reduced instruction set computing ("RISC") processors and complex instruction set computing ("CISC") processors. The operational characteristics on which these categorizations are based define a processor and are collectively referred to as the processor's architecture. More particularly, an architecture is a specification defining the interface between the processor's hardware and the processor's software.
One aspect of a processor's architecture is whether it executes instructions sequentially or out of order. Historically, processors executed one instruction at a time in a sequence. A program written in a high level language was compiled into object code consisting of many individual instructions for handling data. The instructions might tell the processor to load or store certain data from memory, to move data from one location to another, or any one of a number of data manipulations. The instructions would be fetched from memory, decoded, and executed in the sequence in which they were stored. This is known as the "sequential programming model." Out of order execution involves executing instructions in some order different from the order in which they are presented by the program, i.e., out of order or non-sequentially.
The sequential programming model creates what are known as "data dependencies" and "control dependencies." For instance, if one uses the variable x to calculate a result, one needs to know the value of x and that value might depend on results from previously executed instructions. Similarly, a group of instructions might contain two alternative subsets of instructions, only one of which will be executed, depending on some specified condition. Thus, the result of executing the group of instructions will depend on whether a branch is executed. Even out of order execution follows this sequential programming model, and it therefore also creates data and control dependencies.
A second aspect of a processor's architecture is whether it "pipelines" instructions. The processor fetches instructions from memory and feeds them into one end of the pipeline. The pipeline is made of several "stages," each stage performing some function necessary or desirable to process instructions before passing the instruction to the next stage. For instance, one stage might fetch an instruction, the next stage might decode the fetched instruction, and the next stage might execute the decoded instruction. Each stage of the pipeline typically moves the instruction closer to completion.
Some processor pipelines process selected instructions "speculatively." Exemplary speculative execution techniques include, but are not limited to, advanced loads, branch prediction, and predicate prediction. Speculative execution means that instructions are fetched and executed before resolving pertinent control dependencies. Speculative execution requires a prediction as to what instructions are needed depending on whether a branch is taken, executing fetched instructions, and then verifying the execution and prediction. The pipeline executes a series of instructions and, in the course of doing so, makes certain predictions about how control dependencies will be resolved. For instance, if two instructions are to be alternatively executed depending on the value of some quantity, then the pipeline has to guess what that value will be or which instruction will be executed. The pipeline then predicts the next instruction to be executed and fetches the predicted instruction before the previous instruction is actually executed.
A pipeline therefore has the tremendous advantage that, while one part of the pipeline is working on a first instruction, a second part of the pipeline can be working on a second instruction. Thus, more than one instruction can be processed at a time, thereby increasing the rate at which instructions can be executed in a given time period. This, in turn, increases the processor throughput.
Verification is one of the pipeline's most significant challenges. At the end of the pipeline, the results from executed instructions are temporarily stored in a buffer until all their data and control dependencies have been actually resolved. The pipeline then checks to see whether any problems occurred. If there are no problems, then the executed instructions are "retired." This is sometimes referred to as "commitment to an architectural state" or "retirement to a committed state." Retirement or commitment signals that all dependencies have been correctly resolved and that the execution results are finalized.
However, no pipeline correctly predicts all eventualities and, when problems occur, they must be repaired. Problems can typically be traced to:
(1) executing an instruction that should not have been executed; PA1 (2) omitting an instruction that should have been executed; or PA1 (3) executing an instruction with incorrect data.
The effects of such problems on subsequent execution of instructions must also be repaired. Once the problem and its effects have been repaired, the pipeline can then process the execution stream correctly.
Most pipelined processors "stall" the pipeline upon detecting a problem. As discussed above, the pipeline is usually divided into several stages. Progress through the stages is governed by a number of latches enabled by a signal generated by a particular part of the pipeline. If a problem is detected, the latches are disabled and the pipeline "stalls" such that the instructions can no longer be transferred into the next stage. The problem and its effects are then repaired, the latches are re-enabled, and the pipeline resumes.
Design considerations now counsel against stall pipelines in some circumstances. A stall pipeline must receive signals from different parts of the pipeline, determine whether the pipeline must stall, and then broadcast the appropriate signal to enable or stall pipeline progression. This determination takes a certain amount of time. New generations of processors are now operating at frequencies that make that amount of time a significant design constraint.
Some processor pipelines "replay" in addition to stalling. Replay is the reexecution of instructions upon detecting an execution problem in the retirement of speculative results. The speculative results are not retired, i.e., used to update the architectural state of the processor, but arc instead ignored. The pipeline corrects the problem and then re-executes the instructions. The new results are then checked for problems and retired.
One such processor is the Alpha 21164 microprocessor, commercially available from Digital Equipment Corporation. The Alpha 21164 stalls only the first three stages of the pipeline. If a problem occurs after the third stage, the Alpha 21164 replays the entire pipeline beginning with the repaired problem instead of stalling the problem in midstream. However, replaying the entire pipeline regardless of the problem can be expensive in terms of time. The Alpha 21164 therefore combines expensive stalling with complex decision-making circuitry necessary to determine when to replay. Also, when the Alpha 21164 replays, it replays the entire pipeline line even though the problem may be localized at some point in the pipeline.
The demand for faster, more powerful processors continually outstrips present technology. The demand pressures all aspects of processor architecture design to become faster, which demand directly implicates pipeline throughput. Thus, there is a need for a new technique for correcting execution problems in a pipelined process.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.